package sort.tool;


import java.util.ArrayDeque;
import java.util.Deque;
import java.util.concurrent.ThreadLocalRandom;

/**
 * 七大排序
 */
public class SevenSort {
    private static final ThreadLocalRandom random = ThreadLocalRandom.current();

    /**
     * 三路快速排序
     * @param arr
     */
    public static void quickSortThreeWay(int[] arr) {
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(arr.length - 1);
        stack.push(0);
        while (!stack.isEmpty()) {
            int left = stack.pop();
            int right = stack.pop();
            if (right - left <= 0) {
                continue;
            }
            int[] indexPs = partitionThreeWay(arr, left, right); // 等于基准值的区间左右索引
            int indexL = indexPs[0] - 1;
            int indexR = indexPs[1] + 1;
            stack.push(right);
            stack.push(indexR);
            stack.push(indexL);
            stack.push(left);
        }
    }

    /**
     * 三路快排的partition方法
     * 将[left,right]最终分为小于基准值的区域，等于基准值的区域，大于基准值的区域
     * @param arr
     * @param left
     * @param right
     * @return
     */
    private static int[] partitionThreeWay(int[] arr, int left, int right) {
        int index = random.nextInt(left, right);
        swap(arr, left, index);
        int p = arr[left];
        // l指向最后一个小于p的元素索引
        // arr[left + 1, l] < p
        int l = left;
        // cur指向当前遍历的元素索引，即等于p区域的下一个位置
        // arr[l + 1, cur) == p
        int cur = l + 1;
        // r指向第一个大于p的元素索引
        // arr[r, right] > p
        int r = right + 1;
        while (cur < r) {
            if (arr[cur] > p) {
                swap(arr, cur, r - 1);
                r --;
            } else if (arr[cur] < p) {
                swap(arr, cur, l + 1);
                l ++;
                cur ++;
            } else {
                cur ++;
            }
        }
        swap(arr, left, l);
        int[] ret = new int[] {l, r - 1};
        return ret;
    }


    /**
     * 二路快速排序
     * @param arr
     */
    public static void quickSortTwoWay(int[] arr) {
        quickSortTwoWay(arr, 0, arr.length - 1);
    }

    /**
     * 对arr数组中[left,right]子区间进行排序
     * @param arr
     * @param left
     * @param right
     */
    private static void quickSortTwoWay(int[] arr, int left, int right) {
        if (right - left <= 0) {
            return;
        }
        // 获取基准值的索引
        int indexP = partitionTwoWay(arr, left, right);
        quickSortTwoWay(arr, left, indexP - 1);
        quickSortTwoWay(arr, indexP + 1, right);
    }

    /**
     * 二路快排：对arr[left, right]子区间操作，不断以基准值p为比较对象，将小于等于p的和大于等于p的进行交换，是该区间是不大于p的都在p的左边、
     * 不小于p的都在p的右边的形式，p找到了整体排序后它的目标位置
     * 有效的解决了基础快速排序遇到的左右子区间长度严重不平衡造成的时间复杂度退化问题
     * @param arr
     * @param left
     * @param right
     * @return
     */
    private static int partitionTwoWay(int[] arr, int left, int right) {
        // 选取随机基准值
        int index = random.nextInt(left, right);
        swap(arr, left, index);
        int p = arr[left];
        int l = left + 1; // arr[left + 1, l) <= p
        int r = right; // arr(r, right] >= p
        while (true) {
            // 从左边开始遍历，找到一个大于或等于p的元素
            while (l <= r && arr[l] < p) {
                l ++;
            }
            // 从右边开始遍历找到一个小于或等于p的元素
            while (l <= r && arr[r] > p) {
                r --;
            }
            if (l >= r) {
                break;
            }
            // 交换左边、和右边找到的两个元素
            swap(arr, l, r);
            l ++;
            r --;
        }
        // r的目标是找到比p小的元素，所以最终它一定是落在了最后一个比p小的元素上，将基准值与该位置交换
        swap(arr, left, r);
        return r;
    }

    /**
     * 快速排序（挖坑填坑法）
     * @param arr
     */
    public static void quickSortDigHole(int[] arr) {
        quickSortDigHole(arr, 0, arr.length - 1);
    }

    /**
     * 挖坑填坑法的排序
     * @param arr
     * @param left
     * @param right
     */
    private static void quickSortDigHole(int[] arr, int left, int right) {
        if (right - left <= 0) {
            return;
        }
        int indexP = partitionDigHole(arr, left, right);
        quickSortDigHole(arr, left, indexP - 1);
        quickSortDigHole(arr,indexP + 1, right);
    }

    private static int partitionDigHole(int[] arr, int left, int right) {
        int index = random.nextInt(left, right);
        swap(arr, left, index);
        int p = arr[left];
        int l = left;
        int r = right;
        while (l < r) {
            // 必须先从后向前遍历
            while (l < r && arr[r] >= p) { // l不能等于r，因为后面要覆盖值就乱了！
                r --;
            }
            arr[l] = arr[r];
            while (l < r && arr[l] <= p) {
                l ++;
            }
            arr[r] = arr[l];
        }
        arr[l] = p;
        return l;
    }

    /**
     * 快速排序
     * @param arr
     */
    public static void quickSort(int[] arr) {
        quickSortInternal(arr, 0, arr.length - 1);
    }

    /**
     * 将 arr中[left, right]区间上的元素进行排序
     * @param arr
     * @param left
     * @param right
     */
    private static void quickSortInternal(int[] arr, int left, int right) {
//        if (right - left < 1) {
//            return;
//        }
        // 优化，排序序列长度较小时直接使用插入排序
        if (right - left <= 15) {
            bsInsertionSort(arr, left, right);
            return;
        }
        // 获取分区点（基准值的索引）
        int indexP = partition(arr, left, right);
        // 再对[left, indexP - 1] ,[indexP + 1, right]惊醒排序
        quickSortInternal(arr, left, indexP - 1);
        quickSortInternal(arr, indexP + 1, right);
    }

    /**
     * 将arr[left, right]子区间上小于基准值的元素放在基准值的左边，大于基准值的放于右边，则基准值就放到了整体排序后它的目标位置
     * @param arr
     * @param left
     * @param right
     * @return 返回基准值索引
     */
    private static int partition(int[] arr, int left, int right) {
        // 取基准值
        // 问题：若数组是一个有序的数组，不管取第一个值还是最后一个值，快速排序时间复杂度都会退化为O(N^2)，数组过长时递归会栈溢出
        // 解决：随机取一个基准值、(左中右)三数取中法
        int randomIndex = random.nextInt(left, right);
        swap(arr, randomIndex, left);
        int p = arr[left];
        int less = left; // less是小于基准值p的元素序列中最后一个元素的索引
        for (int i = left + 1; i <= right; i++) {
            // i是当前正在遍历的元素的索引
            if (arr[i] < p) {
                swap(arr, i, less + 1);
                less ++;
            }
        }
        // 最终将p交换到小大子区间的中间
        swap(arr, left, less);
        return less;
    }

    /**
     * 非递归实现快速排序
     * @param arr
     */
    public static void quickSortNonRecursive(int[] arr) {
        // 使用栈来控制子区间的范围
        Deque<Integer> stack = new ArrayDeque<>();
        // 先进后出
        // 先入右后入左
        stack.push(arr.length - 1);
        stack.push(0);
        while (!stack.isEmpty()) {
            int left = stack.pop();
            int right = stack.pop();
            if (right - left <= 0) {
                // 这时区间内只有一个元素，无需再分
                continue;
            }
            int indexP = partition(arr, left, right);
            // 先入右子区间
            stack.push(right);
            stack.push(indexP + 1);
            stack.push(indexP - 1);
            stack.push(left);
        }
    }



    /**
     * 归并排序
     * @param arr
     */
    public static void mergeSort(int[] arr) {
        // 将数组拆分，知到每个数组长度为一。排序并合并相邻两个数组直到为一整个数组为止
        mergeSortInternal(arr, 0, arr.length - 1);
    }

    /**
     * 对数组内部不断拆分排序合并
     * @param arr
     * @param left
     * @param right
     */
    private static void mergeSortInternal(int[] arr, int left, int right) {
//        if (right - left < 1) {
//            // 当拆分为子区间仅剩1个元素时进行排序合并
//            return;
//        }
        // 优化：当子区间足够小的时候进行插入排序
        if (right - left <= 15) {
            bsInsertionSort(arr, left, right);
            return;
        }
        // 将数组拆分为[left, mid] [mid + 1, right]两个小区间
        int mid = left + ((right - left) >> 1);
        // 再不断对两个小区间进行拆分排序
        mergeSortInternal(arr, left, mid);
        mergeSortInternal(arr, mid + 1, right);
        // 至此两个小区间已经都有序了，将整个数组进行排序合并
//        merge(arr, left, mid, right);
        // 优化
        if (arr[mid] > arr[mid + 1]) {
            merge(arr, left, mid, right);
        }
    }

    /**
     * 对数组left到right序列的元素进行拆分插入排序
     * @param arr
     * @param left
     * @param right
     */
    private static void bsInsertionSort(int[] arr, int left, int right) {
        for (int i = 1 + left; i <= right; i++) {
            int low = left;
            int high = i;
            int num = arr[i];
            while (low < high) {
                int mid = low + ((high - low) >> 1);
                if (num < arr[mid]) {
                    high = mid;
                } else {
                    low = mid + 1;
                }
            }
            for (int j = i; j > low; j--) {
                arr[j] = arr[j - 1];
            }
            arr[low] = num;
        }
    }

    /**
     * 合并arr中[left, mid],[mid + 1, right]两个小区间进行排序合并
     * @param arr
     * @param left
     * @param mid 包含在右区间
     * @param right
     */
    private static void merge(int[] arr, int left, int mid, int right) {
        int[] tmp = new int[right - left + 1];
        for (int i = left; i <= right; i++) {
            tmp[i - left] = arr[i];
        }
        int index1 = left, index2 = mid + 1;
        // 将每次找到的最小值放入较小索引处
        for (int i = left; i <= right; i++) {
            if (index1 > mid) {
                // 左区间已经处理完毕
                arr[i] = tmp[index2 - left];
                index2 ++;
            } else if (index2 > right) {
                // 右区间已经处理完毕
                arr[i] = tmp[index1 - left];
                index1 ++;
            } else if (tmp[index1 - left] <= tmp[index2 - left]) {
                // 如果有两个相等的元素，取等号就可以保持原先的相对位置，保证了归并排序的稳定性
                arr[i] = tmp[index1 - left];
                index1 ++;
            } else {
                arr[i] = tmp[index2 - left];
                index2 ++;
            }
        }
    }

    /**
     * 归并排序的非递归实现
     * @param arr
     */
    public static void mergeSortNonRecursive(int[] arr) {
        // 递归实现将数组拆分为多个长度为一的数组进行合并。是自顶向下的
        // 非递归可以直接将数组从头开始每次取长度为一的数组进行排序合并，然后取一对长度为2 * 1的...2 * size...直到取到整个数组的长度时整个数组有序
        // size代表每次取数组中连续个元素的个数
        int len = arr.length;
        for (int size = 1; size <= len; size = 2 * size) {
            // i是左区间起始的位置
            for (int i = 0; i < len; i = i + size * 2) {
                // [left, mid] [mid + 1, right]
                merge(arr, i, i + size - 1, Math.min(i + size * 2 - 1, len - 1)); // 注意防止right越界
            }
        }
    }

    /**
     * 希尔排序
     * @param arr
     */
    public static void shellSort(int[] arr) {
        int gap = arr.length >> 1; // gap一般选取数组长度的一半或者三分之一
        // 预处理阶段，不断将数组分为多个小数组，并让每个小数组有序，当数组长度为1时整个数组就变成了一个近乎有序的数组，然后全部进行一次插入排序即可
        while (gap > 1) {
            sortByGap(gap, arr);
            gap = gap >> 1;
        }
        insertionSort(arr);
    }

    /**
     * 对数组中间隔gap的元素进行排序
     * @param gap
     * @param arr
     */
    private static void sortByGap(int gap, int[] arr) {
        // 从gap开始遍历，gap位置的前方是没有对应间隔gap的元素的
        for (int i = gap; i < arr.length; i++) {
            // 倒着找间隔gap的元素进行比较将较大值换入靠后
            // j - gap >= 0 && arr[j - gap] > arr[j] 前面间隔gap的元素已经有序遇到第一个较小的值则停止遍历
            for (int j = i; j - gap >= 0 && arr[j - gap] > arr[j]; j -= gap) {
                swap(arr, j - gap, j);
            }
        }
    }

    /**
     * 折半插入排序
     * @param arr
     */
    public static void bsInsertionSort(int[] arr) {
        // 由于直接插入排序中涉及在 有序序列 中查找元素的操作，可以使用二分查找法优化
        for (int i = 1; i < arr.length; i++) {
            // [0,i)排序区间
            int left = 0;
            int right = i; // 现在理解的是为了让最终结果落在left上所以让right都取到待查找区间的后面一个位置
            int num = arr[i];
            while (left < right) {
                int mid = left + ((right - left) >> 1);
                if (num < arr[mid]) {
                    right = mid;
                }else {
                    left = mid + 1;
                }
            }
            // left就是要插入的位置
            // 将left到位置统一向后挪动
            for (int j = i; j > left; j--) {
                arr[j] = arr[j - 1];
            }
            arr[left] = num;
        }
    }

    /**
     * 直接插入排序
     * @param arr
     */
    public static void insertionSort(int[] arr) {
        // 维持一个前（后）边有序区间[0...i)，每次将待排序区间[i...arr.length - 1]中取第一个值（i）插入到有序区间合适的位置
        for (int i = 1; i < arr.length; i++) {
//            for (int j = i; j > 0; j--) { // 交换的话要将j与j-1交换，所以j不能取零
//                if (arr[j] >= arr[j - 1]) {
//                    // 为了保证稳定性两个数相等的时候不交换
//                    break;
//                }
//                swap(arr, j, j- 1);
//            }

            for (int j = i; j > 0 && arr[j] < arr[j - 1] ; j--) {
                swap(arr, j, j - 1);
            }
        }
    }

    /**
     * 双向选择排序
     * @param arr
     */
    public static void selectionSortTwoWay(int[] arr) {
        // 遍历一次中分别选取最大值以及最小值，将最小值放于待排序序列的前边，最大值放于待排序序列的后边
        int low = 0;
        int high = arr.length - 1;
        while (low < high) {
            // 开始时将最大最小值的索引都放于待排序区间第一个索引
            int minIndex = low;
            int maxIndex = low;
            for (int i = low + 1; i <= high; i++) {
                if (arr[i] < arr[minIndex]) {
                    minIndex = i;
                }
                if (arr[i] > arr[maxIndex]) {
                    maxIndex = i;
                }
            }
            swap(arr, minIndex, low);
            if (maxIndex == low) {
                maxIndex = minIndex;
            }
            swap(arr, maxIndex, high);
            low ++;
            high --;
        }
    }

    /**
     * 选择排序
     * @param arr
     */
    public static void selectionSort(int[] arr) {
        // 遍历数组选择最小（最大）的放在前边（后边）有序序列的后边（前边）
        for (int i = 0; i < arr.length; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                // [0...i)有序序列 [i...arr.length]待排序序列
                // 取待排序序列中的最小值放于i处
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            swap(arr, i, minIndex);
        }
    }

    /**
     * 冒泡排序
     * @param arr
     */
    public static void bubblingSort(int[] arr) {
        int len = arr.length;
        for (int i = 0; i < len - 1; i++) { // 最后只剩一个数整个数组已经有序了不用再排
            // 外层循环控制趟数
            boolean flag = false; // 若某次排序已经有序，控制不进行下一次比较.
            for (int j = 0; j < len - 1 - i; j++) {
                // 内层循环控制交换，将当前最大值放于排序区间的后一个位置
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                    flag = true;
                }
            }
            if (!flag) {
                break;
            }
        }
    }

    /**
     * 堆排序
     * @param nums
     */
    public static void heapSort(int[] nums) {
        int len = nums.length;
        // 将数组中非叶子通过下沉操作将数组转化为最大堆的形式
        // 从最后一个节点的父节点开始，也就是最后一个非叶子节点开始
        for (int i = (len - 1 - 1) / 2; i >= 0; i--) {
            siftDown(nums, i, len);
        }
        // 不断替换堆顶元素和限制范围内的的最后一个元素，就将当前最大值存到属于它的位置（数组同步操作），然后对堆顶元素进行下沉操作维持一个最大堆便于下次取到最大值
        for (int i = len - 1; i > 0; i--) {
            swap(nums, 0, i);
            siftDown(nums, 0, i);
        }
    }

    /**
     * 对数组nums中，处于i位置的元素进行下沉操作
     * @param nums
     * @param i
     * @param len 限制下沉的范围，范围为0到len - 1
     */
    private static void siftDown(int[] nums, int i, int len) {
        while ((i << 1) + 1 < len) { // 当还有子树
            int k = (i << 1) + 1;
            if (k + 1 < len && nums[k + 1] > nums[k]) {
                k = k + 1;
            }
            if (nums[i] >= nums[k]) {
                // 若节点值大于等于子节点中最大值，则下沉结束
                return;
            }
            swap(nums, i, k);
            i = k;
        }
    }

    /**
     * 将数组nums中处于i位置和处于k位置的值进行交换
     * @param nums
     * @param i
     * @param k
     */
    private static void swap(int[] nums, int i, int k) {
        int tmp = nums[i];
        nums[i] = nums[k];
        nums[k] = tmp;
    }
}
